# bubble sort
def bubble_sorted(array):
    swapped=False
    n=len(array)-1
    for i in range(n):
        for j in range(n-i):
            if array[j] > array[j+1]:
                array[j],array[j+1]=array[j+1],array[j]
                swapped=True
        if not swapped:
            break
    return array

# insert sort
def insert_sorted(array):
    def dich_insert(n,array):
        subarray=array
        while len(subarray) > 1:
            if subarray[0]==subarray[-1]:
                break
            mid=len(subarray)//2
            if n>=subarray[mid]:
                subarray=subarray[mid:]
            else:
                subarray=subarray[:mid]
        if n<subarray[0]:
            tag=array.index(subarray[0])
        else:
            tag=array.index(subarray[0])+len(subarray)
        array=array[:tag]+[n]+array[tag:]
        return array
    for i in range(1,len(array)):
        array[:i+1]=dich_insert(array[i],array[:i])
    return array

# select sort
def select_sorted(array):
    for i in range(len(array)):
        p=array.index(min(array[i:]))
        array[i],array[p]=array[p],array[i]
    return array

# shell sort
def shell_sorted(array):
    n=len(array)
    d=n//2
    while d>0:
        for i in range(d,n):
            temp=array[i]
            j=i
            while j>=d and array[j-d] > temp:
                array[j]=array[j-d]
                j-=d
            array[j]=temp
        d=d//2
    return array

# fast sort
def quick_sorted(array,start,end):
    def get_base(array,left,right):
        base=array[left]
        while left<right:
            while left<right and array[right]>=base:
                right-=1
            array[left]=array[right]
            while left<right and array[left]<=base:
                left+=1
            array[right]=array[left]
        array[left]=base
        return left
    if start<end:
        p=get_base(array,start,end)
        quick_sorted(array,start,p-1)
        quick_sorted(array,p+1,end)
    return array
